package 代码记录.指定公司代码练习记录.华为_2024.分值100.第36start;

import java.util.Scanner;

/**
 * @author zx
 * @create 2024-02-16 13:17
 * 自己之前的代码，搜索矩阵问题(二刷)
 */
public class 地图寻宝_70 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int k = sc.nextInt();
        boolean[][] arr = new boolean[m][n];
        int res = dfs(arr,0, 0,k);//注意这里,和之前的不一样：(i,j) -> (0,0)
        System.out.println(res);
    }
    private static int dfs(boolean[][] arr, int i, int j, int k) {
        if(i < 0 || i >= arr.length || j < 0 || j >= arr[0].length) {
            return 0;
        }
        if(arr[i][j] || bitSum(i) + bitSum(j) > k){
            return 0;
        }
        arr[i][j] = true;
        return 1 + dfs(arr,i - 1, j, k) + dfs(arr, i + 1,j, k) + dfs(arr,i,j - 1,k) + dfs(arr,i,j + 1,k);
    }
    //数位之和计算
    private static int bitSum(int n) {
        int sum = 0;
        while(n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}
